# Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

## Item Preview

### Flag this item for

#
texts
Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Publication date
2011-11-07

Collection
arxiv; additional_collections; journals

Language
English

We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt(\gamma)) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in time \tilde{O}(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute \exp(-L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to \exp(-A)v for a class of PSD matrices A and a given vector u, in time roughly \tilde{O}(m_A), where m_A is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting SDD matrices in \tilde{O}(m_A) time. Finally, we prove e^{-x} can be uniformly approximated up to a small additive error, in a non-negative interval [a,b] with a polynomial of degree roughly \sqrt{b-a}. While this result is of independent interest in approximation theory, we show that, via the Lanczos method from numerical analysis, it yields a simple algorithm to compute \exp(-A)v for PSD matrices that runs in time roughly O(t_A \sqrt{||A||}), where t_A is the time required for computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(\sqrt(\gamma)), for balanced separator that runs in time \tilde{O}(m/\sqrt(\gamma)). This latter algorithm matches the running time, but improves on the approximation guarantee of the algorithm by Andersen and Peres.

Identifier
arxiv-1111.1491

Identifier-ark
ark:/13960/t92828r12

Ocr
ABBYY FineReader 9.0

Ppi
300

Scanner
Internet Archive Python library 0.3.2

See also
arXiv

##
comment
Reviews

There are no reviews yet. Be the first one to
write a review.

##### SIMILAR ITEMS (based on metadata)

Source: http://arxiv.org/abs/math/0603606v1

Arxiv.org

by
Paul G. Constantine; Eric T. Phipps

texts

######
eye 39

###### favorite 0

###### comment 0

Source: http://arxiv.org/abs/1110.0058v2

Source: http://arxiv.org/abs/1301.2102v2

Arxiv.org

by
Samuel Fiorini; Gwenaël Joret

texts

######
eye 30

###### favorite 0

###### comment 0

Source: http://arxiv.org/abs/1104.1080v1

Source: http://arxiv.org/abs/math/0309194v1

Source: http://arxiv.org/abs/quant-ph/0011049v1

Source: http://arxiv.org/abs/1111.0483v1

Source: http://arxiv.org/abs/0804.3860v2

Source: http://arxiv.org/abs/cond-mat/9712283v1

Arxiv.org

by
Sourav Chatterjee; Jason Fulman; Adrian Rollin

texts

######
eye 37

###### favorite 0

###### comment 0

Source: http://arxiv.org/abs/math/0605552v2